package com.linran.structure_algorithm.算法.lesson2_排序;

import java.time.Duration;
import java.time.LocalDateTime;
import java.util.Arrays;

/**
 * 希尔排序
 */
public class FourShellSort {
    public static void main(String[] args) {
//        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000 - 1; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }
        LocalDateTime start = LocalDateTime.now();
        shellSort2(arr);
        LocalDateTime end = LocalDateTime.now();
        System.out.println("排序后的数组");
//        System.out.println(Arrays.toString(arr));
        System.out.printf("耗时:%d毫秒%n", Duration.between(start, end).toMillis());
    }

    /*交换法*/
    public static void shellSort1(int[] arr) {
        int temp = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //内部采用冒泡排序(效率低)，频繁发生数据交换
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }

    /*移位法*/
    public static void shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //调整为插入法排序，数据只是移位
                int curIndex = i;
                int curVal = arr[curIndex];
                while (curIndex - gap >= 0 && curVal < arr[curIndex - gap]) {
                    arr[curIndex] = arr[curIndex - gap];
                    curIndex -= gap;
                }
                arr[curIndex] = curVal;
            }
        }
    }


    //使用逐步推到的方式来编写希尔排序(交换式)
    public static void exchangeShellSort(int[] arr) {
//        int temp = 0;
//        // 根据前面的逐步分析，使用循环处理
//        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//            for (int i = gap; i < arr.length; i++) {
//                // 遍历各组中所有的元素(共5组,每组有2个元素)
//                for (int j = i - gap; j >= 0; j -= gap) {
//                    if (arr[j] > arr[j + gap]) {
//                        temp = arr[j];
//                        arr[j] = arr[j + gap];
//                        arr[j + gap] = temp;
//                    }
//                }
//            }
////            System.out.println("希尔排序x轮后=" + Arrays.toString(arr));
//        }
//        //希尔排序的第1轮排序
//        //因为第1轮排序，是将10个数据分成了5组
//        for (int i = 5; i < arr.length; i++) {
//            // 遍历各组中所有的元素(共5组,每组有2个元素)
//            for (int j = i - 5; j >= 0; j -= 5) {
//                if (arr[j] > arr[j + 5]) {
//                    int temp = arr[j];
//                    arr[j] = arr[j + 5];
//                    arr[j + 5] = temp;
//                }
//            }
//        }
//        System.out.println("希尔排序1轮后=" + Arrays.toString(arr));
//
//        //希尔排序的第2轮排序
//        //因为第1轮排序，是将10个数据分成了5组
//        for (int i = 2; i < arr.length; i++) {
//            // 遍历各组中所有的元素(共5组,每组有2个元素)
//            for (int j = i - 2; j >= 0; j -= 2) {
//                if (arr[j] > arr[j + 2]) {
//                    int temp = arr[j];
//                    arr[j] = arr[j + 2];
//                    arr[j + 2] = temp;
//                }
//            }
//        }
//        System.out.println("希尔排序2轮后=" + Arrays.toString(arr));
//
//        //希尔排序的第3轮排序
//        //因为第1轮排序，是将10个数据分成了5组
//        for (int i = 1; i < arr.length; i++) {
//            // 遍历各组中所有的元素(共5组,每组有2个元素)
//            for (int j = i - 1; j >= 0; j -= 1) {
//                if (arr[j] > arr[j + 1]) {
//                    int temp = arr[j];
//                    arr[j] = arr[j + 1];
//                    arr[j + 1] = temp;
//                }
//            }
//        }

    }
}
